package com.atguigu.tree;

/**
 * @author shkstart
 * @create 2021-08-16 15:54
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
   //测试创建二叉树
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        //手动赋值二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);
        //测试
//        System.out.println("前序遍历");//1,2,3,5,4
//        binaryTree.preOrder();
//        System.out.println("中序遍历");//2,1,5,3,4
//        binaryTree.infixOrder();
//        System.out.println("后序遍历");//2,5,4,3,1
//        binaryTree.postOrder();
        //查找方法
//        System.out.println("前序查找方法----");
//        HeroNode resNode = binaryTree.preOrderSearch(5);
//        if (resNode!=null){
//            System.out.println("找到了，信息为no="+resNode.getNo()+" name="+resNode.getName());
//        }else {
//            System.out.println("没有找到英雄");
//        }

//        System.out.println("中序查找方法----");
//        HeroNode resNode = binaryTree.infixOrderSearch(5);
//        if (resNode!=null){
//            System.out.println("找到了，信息为no="+resNode.getNo()+" name="+resNode.getName());
//        }else {
//            System.out.println("没有找到英雄");
//        }
//        System.out.println("后序查找方法----");
//        HeroNode resNode = binaryTree.postOrderSearch(5);
//        if (resNode!=null){
//            System.out.println("找到了，信息为no="+resNode.getNo()+" name="+resNode.getName());
//        }else {
//            System.out.println("没有找到英雄");
//        }
   //测试删除
        //删除规则：
        // 如果是子节点，那就删除子树
        //如果是叶子节点，那就直接删除该节点就行
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();
        System.out.println("删除前，前序遍历");
        binaryTree.preOrder();
        binaryTree.delNode(5);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder();

    }
}
//创建二叉树
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //删除节点
    public void delNode(int no){
        //保证根节点不为空
        if (root!=null){
            //检查根节点是否是删除节点
            if (root.getNo()==no){
                //如果是，那就置空
                root=null;
            }else {
                //如果不是，那就循环
                root.delNode(no);
            }
        }else {
            System.out.println("空树，不能删除！");
        }
    }
    //前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //后序遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //前序查找
    public HeroNode preOrderSearch(int no){
        if (root!=null){
            return root.preOrderSearch(no);
        }else {
            return null;
        }
    }

    //中序查找
    public HeroNode infixOrderSearch(int no){
        if (root!=null){
            return root.infixOrderSearch(no);
        }else {
            return null;
        }
    }

    //前序查找
    public HeroNode postOrderSearch(int no){
        if (root!=null){
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}
//创建节点
class HeroNode{
    private int no;
    private String name;
    //左右节点默认为空
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
   //删除节点
    public void delNode(int no){
        //检查左节点
        if (this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        //检查右节点
        if (this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        //递归左节点
        if (this.left!=null){
            this.left.delNode(no);
        }
        //递归右节点
        if (this.right!=null){
            this.right.delNode(no);
        }
    }
    //前序遍历
    public void preOrder(){
        //输出父节点
        System.out.println(this);
        //递归向左遍历
        if (this.left!=null){
            this.left.preOrder();
        }
        //递归向右遍历
        if (this.right!=null){
            this.right.preOrder();
        }

    }
    //中序遍历
    public void infixOrder(){
        //递归向左遍历
        if (this.left!=null){
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右遍历
        if (this.right!=null){
            this.right.infixOrder();
        }

    }

    //后序遍历
    public void postOrder(){
        //递归向左遍历
        if (this.left!=null){
            this.left.postOrder();
        }
        //递归向右遍历
        if (this.right!=null) {
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);

    }
    //前序查找法
    public HeroNode preOrderSearch(int no){
        System.out.println("前序遍历查找");
        //比较当前节点是否是该查找的点
        if (this.no==no){
            return this;
        }
        HeroNode resNode=null;
        //如果不是，则向左递归
        if (this.left!=null){
            resNode = this.left.preOrderSearch(no);
        }
        //如果不是等于空，那就返回该查找的对象
        if (resNode!=null){
            return resNode;
        }
        //向左不行，那向右递归
        if (this.right!=null){
            resNode=this.right.preOrderSearch(no);
        }
        //无论行不行，哪怕为空也可以返回
        return resNode;
    }
    //中序查找法
    public HeroNode infixOrderSearch(int no){
        HeroNode resNode=null;
        //向左递归
        if (this.left!=null){
            resNode=this.left.infixOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        //开始一一比对
        System.out.println("中序遍历查找");
        if (this.no==no){
            return this;
        }
        //向右递归
        if (this.right!=null){
            resNode=this.right.infixOrderSearch(no);
        }
        return resNode;

    }
    //后序查找法--唯一不同，需要两次比较
    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;

        //向左递归
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //向右递归
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //开始一一比对
        System.out.println("后序遍历查找");
        if (this.no == no) {
            return this;
        }

        return resNode;
    }
}
